import java.util.Random;

class Solution {
    public void sortColors(int[] nums) {
        func(nums,0,nums.length-1);
    }

    public void func(int[] nums,int l,int r){
        if(l>=r) return;
        int n=nums[new Random().nextInt((r-l+1))+l];
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<n) swap(nums,i++,++left);
            else if(nums[i]==n) i++;
            else swap(nums,i,--right);
        }
        func(nums,l,left);
        func(nums,right,r);

    }

    public void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;

    }
}


class Solution1 {
    public int findKthLargest(int[] nums, int k) {
        return pation(nums,0,nums.length-1,k);
    }

    public int pation(int[] nums,int l,int r,int k){
        if(l>=r) return nums[l];
        int left=l-1,right=r+1,i=l;
        int key=nums[new Random().nextInt(r-l+1)+l];
        while(i<right){
            if(nums[i]<key) swap(nums,i++,++left);
            else if(nums[i]==key) i++;
            else swap(nums,i,--right);
        }

        if((r-right+1)>=k) return pation(nums,right,r,k);
        else if(k<=(r-left)) return key;
        else return pation(nums,l,left,k-r+left);

    }

    public void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;

    }
}

